import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by zhangjinrui on 17/6/27.
 */

class TrieNode{
    char v;
    int cnt;
    TrieNode[] children;

    public TrieNode(char v){
        this.v = v;
        cnt = 0;
        children = new TrieNode[26];
    }
}

public class Solution524 {

    public static void main(String args[]){
        Solution524 s = new Solution524();
        System.out.println(s.findLongestWord("abpcplea", Arrays.asList(new String[]{"ale","apple","monkey","plea"})));
    }

    public int findLongestWord(String s, List<String> d) {
        TrieNode root = new TrieNode('*');
        for(String ts : d){
            build(root, ts);
        }

        char[] seq = s.toCharArray();
        int maxv = 0;
        for(int i = 0; i < 26; i ++){
            maxv = max(maxv, dfs(root.children[i], seq, 0, 1));
        }
        return maxv;
    }

    public int dfs(TrieNode node, char[] seq, int st, int len){
        if(node == null){
            return 0;
        }
        for(; st < seq.length ; st ++){
            if(seq[st] == node.v){
                break;
            }
        }
        if(st == seq.length){
            return 0;
        }

        int maxv = 0;
        if(node.cnt != 0){
            maxv = max(maxv, len);
        }

        for(int i = 0 ; i < 26 ; i ++){
            maxv = max(maxv, dfs(node.children[i], seq, st + 1, len + 1));
        }
        return maxv;
    }

    public void build(TrieNode root, String s){
        TrieNode cur = root;
        for(int i = 0 ; i < s.length() ; i ++){
            if (cur.children[s.charAt(i) - 'a'] == null){
                TrieNode node = new TrieNode(s.charAt(i));
                cur.children[s.charAt(i) - 'a'] = node;
            }
            cur = cur.children[s.charAt(i) - 'a'];
        }
        cur.cnt ++;
    }

    public int max(int a, int b){
        return a > b ? a : b;
    }


}
